/*
 * File:   main.c
 * Authors: Stephen Hoeffner
 *          Joe Morreale
 *          Michael Schroeder
 *
 * Created on December 7, 2010, 9:40 PM
 */

#include <omp.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define ROWS 5 // rows of board (EVEN)
#define COLS 5 // columns of board (EVEN)
#define PIECE_ROWS 2 // rows of pieces per side

int b_victories=0, r_victories=0, longest_game=0;
int shortest_game=ROWS*COLS*ROWS;  // just had to be bigger than possible

// the game_state contains all information about any given game at any given time necessary to find moves
struct game_state {
        char board[ROWS][COLS]; // the game board
        int moves;  // counts how many moves have occurred
        char turn; // keeps track of if its red's turn or black's turn
        int recursion_enabled; // recursion enabled by default.  disabled when creating a game_state list.
        struct game_state* next_gs; // linked list of game_states for parallel assignment
        struct game_state* parent;
};

struct location {
        int row;
        int col;
};

// print the game board
void printBoard(struct game_state gs) {
        int i, j, k;
        printf("\n");
        for (k = 0; k < COLS+2; k++) printf("#");
        printf("\n");
        for (i = 0; i < ROWS; i++) {
                printf("#");
                for (j = 0; j < COLS; j++) {
                        if (gs.board[i][j] == ' ')
                                printf("+"); // what to print in the empty spaces
                        else
                                printf("%c", gs.board[i][j]);
                }
                printf("#");
                printf("\n");
        }
        for (k = 0; k < COLS+2; k++) printf("#");
        printf("\n");
}

// print the state of the game
void printGameState(struct game_state gs) {
        printBoard(gs);
        printf("Moves made so far: %d\n", gs.moves);
        printf("Turn: %c\n", gs.turn);
}

void add_gs(struct game_state* gs, struct game_state* gs_spawn) {
        while (gs->parent != NULL) { // find root node, which is where the game_state linked list root is attached
                gs = gs->parent;
        }
        while (gs->next_gs != NULL) { // travel down the linked list to the end
                gs = gs->next_gs;
        }
        gs->next_gs = (struct game_state *)malloc(sizeof(struct game_state));
        gs->next_gs = gs_spawn; // gs_spawn contains correct data, just need to add it
        gs->next_gs->next_gs = NULL; // make sure last element has NULL next pointer
        gs->next_gs->moves = gs_spawn->moves; // this might work once i set moves manually before the malloc
}

// for testing
struct game_state test_board(struct game_state gs) {
        int i, j;
        for (i = 0; i < ROWS; i++) {
                for (j = 0; j < COLS; j++) {
                                        gs.board[i][j] = ' ';  // empty spaces
                }
        }
        gs.board[0][COLS] = 'B';
        gs.board[ROWS][0] = 'R';
        return (gs);
}

// set pieces on the board for a new game
void newBoard(struct game_state* gs) {

        char new_board[ROWS][COLS];
        int i, j;
        #pragma omp parallel for private (i, j)
        for (i = 0; i < ROWS; i++) {
                for (j = 0; j < COLS; j++) {
                        if ( (i%2) != (j%2) ) { // pieces are only at (odd, even) and (even, odd) locations
                                if (i < PIECE_ROWS)
                                        gs->board[i][j] = 'B';  // fill top pieces (black)
                                else if (i > ROWS-PIECE_ROWS-1)
                                        gs->board[i][j] = 'R';  // fill bottom pieces (red)
                                else {
                                        gs->board[i][j] = ' ';  // empty spaces
                                }
                        }
                        else
                                gs->board[i][j] = ' '; // empty spaces that are always empty
                }
        }
}

// initialize new game
void newGame(struct game_state* gs) {
        newBoard(gs);
        gs->moves = 0;
        gs->turn = 'R'; // whose turn is it first
        gs->recursion_enabled = 1; // recursion is enabled by default (only disabled for making a gs_list)
        gs->next_gs = NULL; // root game_state starts alone
        gs->parent = NULL; // root game_state has no parents
}

// return location up and left of passed location
struct location up_left(struct location loc) {
        loc.row--;
        loc.col--;
        return loc;
}

// return location up and right of passed location
struct location up_right(struct location loc) {
        loc.row--;
        loc.col++;
        return loc;
}

// return location down and left of passed location
struct location down_left(struct location loc) {
        loc.row++;
        loc.col--;
        return loc;
}

// return location down and right of passed location
struct location down_right(struct location loc) {
        loc.row++;
        loc.col++;
        return loc;
}

// for checking if a board location exists
int exists(struct location loc) {
        if (loc.row > ROWS-1) return 0;
        else if (loc.row < 0) return 0;
        else if (loc.col > COLS-1) return 0;
        else if (loc.col < 0) return 0;
        else return 1;
}

// dont use yet, might not use.  just returns color of enemy.
char getEnemy(char myColor) {
        if (myColor == 'R') return 'B';
        else if (myColor == 'B') return 'R';
        else return ' ';
}

void make_move(struct game_state* gs, struct location current_loc, struct location new_loc) {
        struct game_state* gs_spawn;
        gs_spawn = (struct game_state *)malloc(sizeof(struct game_state));
        *gs_spawn = *gs; // spawn a new game_state every time a move is made
        gs_spawn->parent = gs; // keep track of parent
        gs_spawn->moves++;

        gs_spawn->board[current_loc.row][current_loc.col] = ' '; // leave old space empty
        gs_spawn->board[new_loc.row][new_loc.col] = gs_spawn->turn; // occupy new space
        if (abs(current_loc.row - new_loc.row) == 2) { // check if this is is a jump move
                int middle_row, middle_col;
                middle_row = (current_loc.row+new_loc.row)/2; // averaging the two locations to find the middle row
                middle_col = (current_loc.col+new_loc.col)/2; // averaging the two locations to find the middle col
                gs_spawn->board[middle_row][middle_col] = ' '; // get rid of jumped piece
        }

        gs_spawn->turn = getEnemy(gs_spawn->turn); // change turns
        if (gs->recursion_enabled == 1)  // not trying to make a gs_list, play out the game recursively
                traverseBoard(gs_spawn);  // RECURSION
        else if (gs->recursion_enabled == 0) { // trying to make a gs_list, add spawn to the list
                add_gs(gs, gs_spawn);// add gs_spawn to gs_list
        }
}

// return number of moves a piece at a specific location can make
int get_moves(struct game_state* gs, struct location loc) {
        int k=0;
        if (gs->turn == 'R') { // if red's turn

                // defines regular one-square moving (not taking pieces)
                if (exists(up_left(loc)))  // check if up and left exists
                        if (gs->board[up_left(loc).row][up_left(loc).col] == ' ') {  // if space is empty
                                k++; // move can be made
                                make_move(gs, loc, up_left(loc));
                        }
                if (exists(up_right(loc)))  // check if up and right exists
                        if (gs->board[up_right(loc).row][up_right(loc).col] == ' ') {  // if space is empty
                                k++; // move can be made
                                make_move(gs, loc, up_right(loc));
                        }

                // defines two-square moving (jumping and taking an enemy pieces)
                if (exists(up_left(up_left(loc))))  // check if landing space exists
                        if (gs->board[up_left(up_left(loc)).row][up_left(up_left(loc)).col] == ' ') {  // check if landing space is empty
                                if (gs->board[up_left(loc).row][up_left(loc).col] == 'B') {  // check if jumped space contains an enemy piece
                                        k++; // move can be made
                                        make_move(gs, loc, up_left(up_left(loc)));
                                }
                        }
                if (exists(up_right(up_right(loc))))  // check if landing space exists
                        if (gs->board[up_right(up_right(loc)).row][up_right(up_right(loc)).col] == ' ') {  // check if landing space is empty
                                if (gs->board[up_right(loc).row][up_right(loc).col] == 'B') {  // check if jumped space contains an enemy piece
                                        k++; // move can be made
                                        make_move(gs, loc, up_right(up_right(loc)));
                                }
                        }
        }

        else if (gs->turn == 'B') { // if black's turn

                // defines regular one-square moving (not taking pieces)
                if (exists(down_left(loc)))  // check if down and left exists
                        if (gs->board[down_left(loc).row][down_left(loc).col] == ' ') {  // if space is empty
                                k++; // move can be made
                                make_move(gs, loc, down_left(loc));
                        }
                if (exists(down_right(loc)))  // check if down and right exists
                        if (gs->board[down_right(loc).row][down_right(loc).col] == ' ') { // if space is empty
                                k++; // move can be made
                                make_move(gs, loc, down_right(loc));
                        }

                // defines two-square moving (jumping and taking an enemy pieces)
                if (exists(down_left(down_left(loc))))  // check if landing space exists
                        if (gs->board[down_left(down_left(loc)).row][down_left(down_left(loc)).col] == ' ') {  // check if landing space is empty
                                if (gs->board[down_left(loc).row][down_left(loc).col] == 'R') {  // check if jumped space contains an enemy piece
                                        k++; // move can be made
                                        make_move(gs, loc, down_left(down_left(loc)));
                                }
                        }
                if (exists(down_right(down_right(loc))))  // check if landing space exists
                        if (gs->board[down_right(down_right(loc)).row][down_right(down_right(loc)).col] == ' ') { // check if landing space is empty
                                if (gs->board[down_right(loc).row][down_right(loc).col] == 'R') { // check if jumped space contains an enemy piece
                                        k++; // move can be made
                                        make_move(gs, loc, down_right(down_right(loc)));
                                }
                        }
        }

        return k;
}

// goes through every space on the board
// returns total number of moves that can be made by the team whose turn it is (which teams turn is stored in the game state)
int traverseBoard(struct game_state* gs) {
        int i, j;
        int moves=0, total_moves=0;
        char turn = gs->turn; // whose turn it is
        struct location loc;

        // go through every space
        // TODO: Parallel this loop
	#pragma omp parallel for private(i, j) firstprivate(gs, turn, loc) //reduction(+:total_moves)
        for (i=0; i<ROWS; i++) {
                for (j=0; j<COLS; j++) {
                        moves=0;
                        if (gs->board[i][j] == turn) { // finding pieces of the right color (based on whose turn it is)
                                loc.row = i;
                                loc.col = j;
                                moves = get_moves(gs, loc);  // how many moves can this specific piece make
                                total_moves += moves;
                        }
                }
        }

        // Victory condition is enemy cannot make a move (through being stuck or from lack of pieces
        // since total_moves visits every single board location and returns the number of moves which can be made from that location, if it is zero, then no moves can be made
        if (total_moves == 0) {
                if (gs->moves > longest_game)
                        longest_game = gs->moves;  // set longest move
                if (gs->moves < shortest_game)
                        shortest_game = gs->moves;  // set shortest move
                if (gs->turn == 'R') { // black wins by forcing red to not have any moves
                        b_victories++;
                        //printf("\nBoard at time of victory for Black:");
                        //printGameState(gs);
                }

                else if (gs->turn == 'B') { // red wins by forcing black to not have any moves
                        r_victories++;
                        //printf("\nBoard at time of victory for Red:");
                        //printGameState(gs);
                }

        }
        return total_moves;
}

void print_gs_list(struct game_state gs, int j) {
        int i=1;
        printf("All game_states in linked list, starting at location %d:\n", j);
        while (gs.next_gs != NULL) {
                if (i >= j) {
                        printf("\nGame State #%d:", i-j+1);
                        printGameState(gs);
                }
                gs = *gs.next_gs;
                i++;
        }
        printf("\nGame State #%d:", i-j+1);
        printGameState(gs);
}

int get_list_length(struct game_state gs) {
        int i=1;
        while (gs.next_gs != NULL) {
                gs = *gs.next_gs;
                i++;
        }
        return i;
}


// returns the i-th game state from the game_state list
struct game_state* get_gs_from_list(struct game_state* gs, int i) {
        int j;
        for (j = 1; j < i; j++)
                if (gs->next_gs != NULL)
                        gs = gs->next_gs;
        return gs;
}

struct boundary {
        int first;
        int last;
};

struct boundary make_gs_list(int processors, struct game_state* gs) {
        struct boundary b;
        struct game_state *temp = gs;
        gs->recursion_enabled = 0;  // disable recursion to fill game_state list
        b.first = 1;
        b.last = 1;

        while (b.last - b.first + 1 < processors) { // while we still need more game_states for processors
                traverseBoard(get_gs_from_list(gs, b.first));  // find all possible game_states from passed game_state, add them to the linked list
                if (get_list_length(*gs) - (b.first + 1) + 1 <= processors) {  // if we didn't get too many game states, so update first and last
                        b.first++;
                        b.last = get_list_length(*gs);
                }
                else
                        break;
        }
        return b;
}

int main() {

        printf("\n\n\n\n\n\n\n\n\n\n");
        struct game_state gs;
        int processors = 9;
        printf("Should print out all possible 2 moves games:\n");
        newGame(&gs);
        struct boundary b;
        struct timeval ts, tf;	/* time of day vars */
        long start=0, end=0;

        // returns a structure containing the number of the last element, and the number of the "first relevant" element
        b = make_gs_list(processors, &gs);


        // gs is the first element in the linked list of game_states.
        // however this first element is probably not relevant because it has probably already added all its possible moves to the linked list
        // the first element of the list which is not redundant in this manner is the n'th element, where n = b.first
        // these boundaries are created by the make_gs_list function

        // to get the first of these "relevant" game states:
        struct game_state* new_head;

        // starting at b.first and going through to the end of the linked list will yield a "processors" number of game_states after a call to make_gs_list.
        // the entire list is longer, but anything before b.first is redundant
        new_head = get_gs_from_list(&gs, b.first);

        // to show this works, the following two lines should print the same output (which at the current setup shows all possible first two moves)
        print_gs_list(gs, b.first);
        printf("\n##################################################\n\n");
        print_gs_list(*new_head, 1);
        printf("\n\n\n\n");

        // this is here just to make sure something i did didnt break the game
        printf("THIS STUFF SHOULDNT BREAK:");
        newGame(&gs);
        printGameState(gs);
        gs.recursion_enabled = 1;

        /* Get starting time */
	gettimeofday(&ts,NULL);
	start= ts.tv_sec;

        traverseBoard(&gs);

        /* Get ending time, display results */
	gettimeofday(&tf,NULL);
	end = tf.tv_sec;
	printf("Elapsed time for OpenMP code: %ld seconds\n", end-start);
        
        printf("\nShortest game: %d moves\n", shortest_game);
        printf("Longest game: %d moves\n", longest_game);
        printf("Total red victories: %d\n", r_victories);
        printf("Total black victores: %d\n\n", b_victories);
}
